package org.example.algorithm.range;

/**
 * 描述
 * Alice 和 Bob 在一个漂亮的果园里面工作，果园里面有N棵苹果树排成了一排，这些苹果树被标记成1 - N号。
 * Alice 计划收集连续的K棵苹果树上面的所有苹果，Bob 计划收集连续的L棵苹果树上面的所有苹果。
 * 他们希望选择不相交的部分（一个由 Alice 的K树组成，另一个由鲍勃 Bob 的L树组成），以免相互干扰。你应该返回他们可以收集的最大数量的苹果。
 * a = {1, 3, 5, 2, 8, 7, 6, 10}
 */
public class PickApplesSolution {

    public int pickApples(int[] a, int k, int l) {
        int len = a.length;
        if (k+l > len) {
            return -1;
        }
        //前缀和数组
        int[] prefixSum = new int[len];
        prefixSum[0] = a[0];
        //计算前缀和
        for (int i=1;i<len;i++) {
            prefixSum[i] = prefixSum[i-1] + a[i];
        }
        //[0,i] 最大长度数组
        int[] arrKSum = calPrefixMaxSum(prefixSum, a, k);
        int[] arrLSum = calPrefixMaxSum(prefixSum, a, l);

        //[i+1, len-1] 最大长度数组
        int[] postKSum = calPostMaxSum(prefixSum, a, k);
        int[] postLSum = calPostMaxSum(prefixSum, a, l);
        int maxApple = 0;
        for (int i=0;i+1<len;i++) {
            maxApple = Math.max(maxApple, arrKSum[i] + postLSum[i+1]);
            maxApple = Math.max(maxApple, arrLSum[i] + postKSum[i+1]);
        }
        return maxApple;
    }

    private int[] calPrefixMaxSum(int[] prefixSum, int[] arr, int k) {
        int len = arr.length;
        int[] arrKSum = new int[len];
        //计算前缀和
        for (int i=k-1;i<len;i++) {
            if (i == k - 1) {
                arrKSum[i] = prefixSum[i];
            } else {
                arrKSum[i] = Math.max(arrKSum[i - 1], calSum(prefixSum, i-k+1, i));
            }
        }
        return arrKSum;
    }

    //[i, len-1]最大值
    private int[] calPostMaxSum(int[] prefixSum, int[] arr, int k) {
        int len = arr.length;
        int[] arrKSum = new int[len];
        //计算后缀和
        for (int i=len-k;i>=0;i--) {
            if (i == len-k) {
                arrKSum[i] = calSum(prefixSum, i, len-1);
            } else {
                arrKSum[i] = Math.max(arrKSum[i+1], calSum(prefixSum, i, i+k-1));
            }
        }
        return arrKSum;
    }

    //区间[i,j]总和
    private int calSum(int[] prefixSum, int i, int j) {
        if (i == 0) {
            return prefixSum[j];
        }
        return prefixSum[j] - prefixSum[i-1];
    }

    public static void main(String[] args) {
        PickApplesSolution pickApplesSolution = new PickApplesSolution();
        int[] a = {6, 1, 4, 6, 3, 2, 7, 4};
        int k = 3;
        int l = 2;
        int res = pickApplesSolution.pickApples(a, k, l);
        System.out.println(res);
    }
}
